package com.congee02;

public class MaxTotalFruits {

    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int max = 0;
        int min = Integer.MAX_VALUE;
        for (int[] fruit : fruits) {
            max = Math.max(max, fruit[0]);
            min = Math.min(max, fruit[0]);
        }
        int[] nums = new int[max - min + 1];

        for (int[] fruit : fruits) {
            nums[fruit[0] + min] = fruit[1];
        }

        return process(nums, startPos - min, k);
    }

    private int process(int[] nums, int curPos, int rest) {
        if (curPos >= nums.length || curPos < 0) {
            return 0;
        }
        if (rest == 0) {
            return nums[curPos];
        }
        int t = nums[curPos];
        nums[curPos] = 0;

        int p1 = process(nums, curPos - 1, rest - 1);
        int p2 = process(nums, curPos + 1, rest - 1);

        nums[curPos] = t;

        return  nums[curPos] + Math.max(p1, p2);
    }

}
